觀前提醒：

1. 我預設大家已經先思考並分析過題目，沒啥想法才開始 google 找解題靈感。若無，建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法。
2. 承上，既然已經有思考過了，那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了，那我可能解題想法 & 心得的部分就不會寫太多，免得干擾你的思考。
3. 所有解法都是已經取得系統的 Accepted，但或許不是最優解法，請多包涵。
4. 若對於解法不太懂，可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
5. 最後，歡迎在下面留言指教~教學相長才會進步歐~

題目

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

解題想法

這題其實相當的有意思，他有點像 Maximum Subarray的顛倒版，我們先以上方 Example 2 為例子，陣列為　[7, 1, 5, 3, 6, 4]，故圖示如下:

(來源:LeetCode)

從上圖來看，我們需要在最低的谷之後找到最高的峰，這樣就能滿足題目的要求。

我們簡單拆成以下步驟執行此策略：

1. 建立一個for迴圈，找出最小值在哪裡(若後值比前值小，則儲存後值)。
2. 當最小值出現後，將後續價格依序減去最小值，並同時計算當下獲利為多少，並儲存為 maxMoney。
3. 若當下的 maxMoney，比之前計算的 maxMoney 還大，則儲存當下該迴圈的 maxMoney。

CODE

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let minPrice = Number.MAX_SAFE_INTEGER;
  let maxMoney = 0;
  for (let i = 0; i < prices.length; i++) {
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else if (prices[i] - minPrice > maxMoney) {
      maxMoney = prices[i] - minPrice;
    }
  }
  return maxMoney;
};

心得

這題也是不太困難，只需要多加留意題目的特性，再搭配 Dynamic programming概念來思考，這題應該不會很難解出來才是~

謝謝大家的收看，LeetCode 小學堂我們下次見~